//https://www.nowcoder.com/practice/2a49359695a544b8939c77358d29b7e6?tpId=13&tqId=1517966&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D13
// 思想：重点题目！！！，使用回溯法解决；

#include <iostream>
#include <vector>
#include <climits>
#include <stack>
#include <queue>

using namespace std;

class Solution {
  public:
    bool dfs(vector<vector<char> >& matrix, int n, int m, int i, int j, string word,
             int k, vector<vector<bool> >& flag) {
        if (i < 0 || i >= n || j < 0 || j >= m || (matrix[i][j] != word[k]) ||
                (flag[i][j] == true))
            //下标越界、字符不匹配、已经遍历过不能重复
            return false;
        //k为记录当前第几个字符
        if (k == word.length() - 1)
            return true;
        flag[i][j] = true;
        //该结点任意方向可行就可
        if (dfs(matrix, n, m, i - 1, j, word, k + 1, flag)
                || dfs(matrix, n, m, i + 1, j, word, k + 1, flag)
                || dfs(matrix, n, m, i, j - 1, word, k + 1, flag)
                || dfs(matrix, n, m, i, j + 1, word, k + 1, flag))
            return true;
        //没找到经过此格的，此格未被占用
        flag[i][j] = false;
        return false;
    }
    bool hasPath(vector<vector<char> >& matrix, string word) {
        //优先处理特殊情况
        if (matrix.size() == 0)
            return false;
        int n = matrix.size();
        int m = matrix[0].size();
        //初始化flag矩阵记录是否走过
        vector<vector<bool> > flag(n, vector<bool>(m, false));
        //遍历矩阵找起点
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                //通过dfs找到路径
                if (dfs(matrix, n, m, i, j, word, 0, flag))
                    return true;
            }
        }
        return false;
    }
};
